# Definition for a Node.
class Node(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return None
        node = root
        head = None
        prev = None
        while True:
            if node.left:
                pre_node = node.left
                while pre_node.right:
                    pre_node = pre_node.right
                pre_node.right = node
                next_node = node.left
                node.left = None
                node = next_node
            else:
                if not head:
                    head = node
                if prev:
                    prev.right = node
                    node.left = prev
                next_node = node.right
                while next_node and not next_node.left:
                    next_node.left = node
                    node = next_node
                    next_node = next_node.right
                if not next_node:
                    node.right = head
                    head.left = node
                    break
                else:
                    prev = node
                    node = next_node

